题目分析

这个题目和上一题异曲同工，一个是通过前序和中序构造二叉树，一个是通过中序和后序构造二叉树，小伙伴们可以学习两道题目中的一个，然后用另一个题目练手，看看自己能否解答出来。

递归

我们已知了后序遍历，因此后序遍历的最后一个节点就是当前二叉树的根节点，我们再从中序遍历中找到该节点，那么中序遍历左边的节点都是左子树，中序遍历右边的节点都是右子树。然后根据左子树的节点个数，确定左子树和右子树的后序遍历，递归建树即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        def sub_question(in_left, in_right, post_left, post_right):
            if post_left > post_right:
                return None
            root_val = postorder[post_right]
            root_idx = dic[root_val]
            left_size = root_idx - in_left
            root = TreeNode(root_val)
            root.left = sub_question(in_left, root_idx - 1, post_left, post_left + left_size - 1) 
            root.right = sub_question(root_idx + 1, in_right, post_left + left_size, post_right - 1) 
            return root

        dic = {v: i for i, v in enumerate(inorder)}
        return sub_question(0, len(postorder) - 1, 0, len(inorder) - 1)

刷题总结

题目的难点在于如何根据根节点确定左右子树的中序和后序遍历，难度不大，需要仔细想一想其中的逻辑关系。